// https://leetcode.cn/problems/01-matrix/description/

// 算法思路总结：
// 1. 多源广度优先搜索计算最短距离
// 2. 从所有0的位置同时开始BFS遍历
// 3. 每个位置记录到最近0的距离
// 4. 利用队列按层扩展，保证最短距离
// 5. 时间复杂度：O(m×n)，空间复杂度：O(m×n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>

class Solution 
{
public:
    int m, n;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    typedef pair<int, int> PII;

    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) 
    {
        m = mat.size(), n = mat[0].size();
        vector<vector<int>> dp(m, vector<int>(n, -1));
        queue<PII> q;

        for (int i = 0 ; i < m ; i++)
        {
            for (int j = 0 ; j < n ; j++)
            {
                if (mat[i][j] == 0)
                {
                    q.push({i, j});
                    dp[i][j] = 0;
                }
            }
        }

        while (!q.empty())
        {
            auto [a, b] = q.front();
            q.pop();

            for (int i = 0 ; i < 4 ; i++)
            {
                int x = a + dx[i], y = b + dy[i];
                if (x >= 0 && y >= 0 && x < m && y < n && dp[x][y] == -1)
                {
                    dp[x][y] = dp[a][b] + 1;
                    q.push({x, y});
                }
            }
        }

        return dp;
    }
};

int main()
{
    vector<vector<int>> mat1 = {{0,0,0},{0,1,0},{0,0,0}};
    vector<vector<int>> mat2 = {{0,0,0},{0,1,0},{1,1,1}};

    Solution sol;
    auto vv1 = sol.updateMatrix(mat1);
    auto vv2 = sol.updateMatrix(mat2);

    for (const auto& v : vv1)
    {
        for (const int& num : v)
        {
            cout << num << " ";
        }
        cout << endl;
    }
    cout << endl;

    for (const auto& v : vv2)
    {
        for (const int& num : v)
        {
            cout << num << " ";
        }
        cout << endl;
    }
    cout << endl;

    return 0;
}